package com.demo.java.OD101_150.OD104;

import java.util.Scanner;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【数组二叉树】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/145692530
 */
public class OdMain {
    /**
     * 根据行号计算该行首个元素的索引
     *
     * @param line 行号
     * @return 该行首个元素的索引
     */
    public static int getStartValue(int line) {
        int sumResult = 0;
        int temp = 0;
        // 每一行的元素数是前一行的两倍
        while (line > 1) {
            sumResult += 1 << temp;  // 每一行首元素的索引递增
            temp++;
            line--;
        }
        return sumResult;
    }

    /**
     * 计算该元素所在的行号
     *
     * @param line 元素的索引
     * @return 元素所在的行号
     */
    public static int getLineNumber(int line) {
        int result = 0;
        // 行号是递增的
        while (line > 0) {
            line -= 1 << result;  // 每一行的元素数目递减
            result++;
        }
        return result;
    }

    public static void main(String[] args) {
        try {
            Scanner s = new Scanner(System.in);
            String[] lines = s.nextLine().split(" ");  // 读取输入并拆分为数组
            // 我们首先需要找出最小的叶子节点所在的行
            int minValue = Integer.MAX_VALUE;
            int index = 0;
            // 从第二个元素开始遍历（第一个是根节点，不需要处理）
            for (int j = 1; j < lines.length; ++j) {
                int value = Integer.parseInt(lines[j]);
                if (value < minValue && value != -1) {
                    index = j;
                    minValue = value;
                }
            }

            // 计算最小值所在的行号
            int lineNumber = getLineNumber(index);
            int[] resultArray = new int[lineNumber];  // 用来存储路径

            // 计算该行的第一个元素索引
            int startValue = getStartValue(lineNumber);
            resultArray[lineNumber - 1] = Integer.parseInt(lines[index]);  // 叶子节点的值

            // 计算该叶子节点在当前行的相对位置
            int inLineNum = index - startValue + 1;

            // 更新行号
            --lineNumber;

            // 根据节点在当前行的位置，逐层回溯到根节点
            inLineNum = (inLineNum % 2 == 0) ? inLineNum / 2 : inLineNum / 2 + 1;
            while (lineNumber > 0) {
                startValue = getStartValue(lineNumber);  // 计算上一行首元素的索引
                resultArray[lineNumber - 1] = Integer.parseInt(lines[inLineNum + startValue - 1]);  // 上一层节点的值
                lineNumber--;
                // 更新节点的位置
                inLineNum = (inLineNum % 2 == 0) ? inLineNum / 2 : inLineNum / 2 + 1;
            }

            // 输出结果路径
            for (int j = 0; j < resultArray.length; ++j) {
                System.out.print(resultArray[j] + " ");
            }
        } catch (Exception e) {
            e.printStackTrace();
            System.out.println("input error");  // 处理异常，输出错误信息
        }
    }
}